1. Field of the Invention
The present invention is directed to digital logic design systems. More particularly, the invention is directed to automated digital logic synthesis and placement systems for integrated circuits, and to performance optimization of digital integrated circuits.
2. Background of Related Art
Prior art computer aided design (CAD) systems for the design of integrated circuits (ICs) and the like assist in the design thereof by providing a user with a set of software tools running on a digital computer. In the prior art, the process of designing an integrated circuit on a typical CAD system is done in several discrete steps using different software tools.
The design process can be broadly divided into two phases. The initial phase 100 (shown in FIG. 1) of selecting the right components and connecting them so that the desired functionality is achieved is called logic synthesis. The second phase 200, in which the selected components are placed within the confines of the chip boundaries and the connecting wires are laid out in order to generate the photographic masks for manufacturing, is called physical synthesis.
First, in the logic synthesis phase 100 a schematic diagram of the integrated circuit is entered interactively in Step 110 to produce a digital representation 115 of the integrated circuit elements and their interconnections. This representation 115 may initially be in a hardware description language such as Verilog or VHDL and then translated into a register transfer level (RTL) description in terms of pre-designed functional blocks, such as memories and registers. This may take the form of a data structure called a net list.
Next, a logic compiler 120 receives the net list in Step 125 and, using a component database 130, puts all of the information necessary for layout, verification and simulation into object files whose formats are optimized specifically for those functions.
Afterwards, in Step 135 a logic verifier 140 preferably checks the schematic for design errors, such as multiple outputs connected together, overloaded signal paths, etc., and generates error indications in Step 145 if any such design problems exist. In many cases, the IC designer improperly connected or improperly placed a physical item within one or more cells. In this case, these errors are flagged to enable her to correct the layout cells in Step 150 so that they perform their proper logical operation.
Also, in Step 135 the verification process preferably checks the cells laid out by hand to determine if multiple design rules have been observed. Design rules may include the timing requirements of the circuit, the area occupied by the final design and parameters derived from other rules dictated by the underlying manufacturing technology. These design rules are provided to integrated circuit designers to ensure that a part can be manufactured with a high degree of yield. Most design rules include hundreds of parameters and, for example, include pitch between metal lines, spacing between diffusion regions in the substrate, sizes of conductive regions to ensure proper contacting without electrical short circuiting, minimum widths of conductive regions, pad sizes, and the like. If a design rules violation is identified in Step 150, this violation is preferably flagged to the IC designer so that she can properly correct the cells so that they are in accordance with the design rules in Step 150.
Then, using a simulator 155 the user of the CAD system may prepare a list of vectors representing real input values to be applied to a simulation model of the integrated circuit in Step 160. This representation may be translated into a form which is better suited to simulation. This representation of the integrated circuit is then operated upon by the simulator which produces numerical outputs analogous to the response of a real circuit with the same inputs applied in Step 165. By viewing the simulation results, the user may then determine in Step 170 if the represented circuit will perform correctly when it is constructed. If not, she may re-edit the schematic of the integrated circuit, re-compile it and re-simulate it in Step 150. This process is performed iteratively until the user is satisfied that the design of the integrated circuit is correct.
Then, the human IC designer may present as input to a logic synthesis tool 175 a cell library 180 and a behavioral circuit model. The behavioral circuit model is typically a file in memory which looks very similar to a computer program, and the model contains instructions which logically define the operation of the integrated circuit. The logic synthesis tool 175 maps the instructions from the behavioral circuit model to one or more logic cells from the library 180 to transform the behavioral circuit model to a gate schematic net list 185 of interconnected cells in Step 187. The gate schematic net list 185 is a database having interconnected logic cells which perform a logical function in accordance with the behavioral circuit model instructions. Once the gate schematic net list 185 is formed, it is provided to a place and route tool 205 to begin the second phase of the design process, physical synthesis.
The place and route tool 205 is preferably then used to access the gate schematic net list 185 and the library cells 180 to position the cells of the gate schematic net list 185 in a two-dimensional format within a surface area of an integrated circuit die perimeter. This process is optimized as will be explained in greater detail below. The output of the place and route step may be a two-dimensional physical design file 210 which indicates the layout interconnection and two-dimensional IC physical arrangements of all gates/cells within the gate schematic net list 185. From this, in Step 215 the design automation software can create a set of photographic masks 220 to be used in the manufacture of the IC.
One common goal in chip design involves timing performance. The timing performance of the chip is determined by the time required for signals to propagate from one register to another. Clock signals driven at a certain frequency control storage of data in the registers. The time required for a signal to propagate from one register to another depends on the number of levels of cells through which the signal has to propagate, the delay through each of the cells and the delay through the wires connecting these cells. The logic synthesis phase 100 influences the number of levels and the propagation delay through each cell because in it the appropriate components are selected, while the physical synthesis 200 phase affects the propagation delay through the wires.
During the process of timing optimization during physical design in Step 205, circuit timing is evaluated based on an initial placement and selection of cell strengths. The feedback from the timing analysis is used to drive repeated improvements to the placement software and the selection of the strengths of the cells. The automation software may also perform buffering on some parts of the circuit to optimize the timing performance by inserting repeater cells, i.e., buffers, to speed up certain paths. See, for example, U.S. patent application Ser. No. 09/300,557 to Buch et al., now U.S. Pat. No. 6,553,338. Preferably, the optimization software tentatively applies one such modification, evaluates the timing and other constraints (such as design rules dictating capacitance limits) to determine if the step is acceptable and then makes the change permanent if it is deemed acceptable.
The number of changes to the circuit in terms of change in placement and net list can be numerous during the automatic optimization step 205. In order to evaluate the timing performance and capacitance the automation software needs to construct some reasonable topologies for connecting the nets so that it can make estimates of net capacitances and, from these, timing estimates. A complete routing of all the wires at this stage is very time consuming and impractical. As an alternative, Steiner tree topologies may be used successfully to estimate delays based on placement. However, constructing a Steiner tree also requires an algorithm with quadratic complexity which makes the optimization process very slow and impractical for a large circuit. While it is important to have accurate estimates of the capacitance and delays during the placement and net list optimization step 205, it is also important to be able to compute the delays and capacitance as quickly as possible. Computing the capacitance of a net takes at least linear time as a function of the number of pins in the net. Therefore a linear time algorithm to compute the capacitance is desirable.